package org.example.sward.tooffer;

import org.example.ch04.tree.TreeNode;

import java.util.HashMap;

public class Offer07 {
    int[] preorder ;
    HashMap<Integer,Integer> dict = new HashMap<>();
    public static void main(String[] args) {
        Offer07 offer07 = new Offer07();

        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        TreeNode result = offer07.buildTree(preorder,inorder);
        System.out.println(result.val);
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            dict.put(inorder[i],i);
        }
        return recur(0,0,inorder.length - 1);
    }

    private TreeNode recur(int root, int left, int right) {
        if(left > right){
            return null;
        }
        //建立根节点
        TreeNode node = new TreeNode(preorder[root]);
        //划分根节点，左子树，右子树
        int i = dict.get(preorder[root]);
        //开启左子树递归
        node.left = recur(root + 1,left,i - 1);
        //开启右子树递归
        node.right = recur(root + i - left + 1,i + 1,right);
        //回溯返回根节点
        return node;

    }


}
